1. Field of the Invention
The present invention relates to an information processing device for performing a pipeline process, and more particularly to a technology for pipeline control in branch prediction.
2. Description of the Related Art
In an information processing device which is represented by a microprocessor whose high integration and high clock advance with the progress of a semiconductor technology, recently a pipeline technology for dividing a process when executing one instruction into a plurality of stages and operating the process mechanism of each stage independently and in parallel has been used in order to improve the execution speed of an instruction. In many of the information processing devices, a method provided with a plurality of such pipelines called “super scalar” is adopted and instructions are speculatively executed by a plurality of pipelines.
When performing a pipeline process, several instructions are simultaneously executed like an assembly-line operation. Therefore, if an instruction is branched in another part of memory by a branch instruction, subsequent instructions whose processes are already started must be all discarded and process efficiency degrades. In order to prevent this, branch prediction is conducted in the information processing device. In branch prediction, it is predicted whether a branch instruction branches. If it is likely to branch, a branch destination instruction is inputted to a pipeline.
For such a branch prediction method, a method for recording branch histories in advance and predicting whether an instruction branches, based on this history is used.
In this method, branch intensity is determined referring to a storage area on which is recorded branch prediction information, based on a branch history called a “branch history table (BHT)” and branch prediction is conducted. In this case, a method for using the combination of values (hereinafter called “BHR information”) in an address at the time of instruction fetch (hereinafter called “FPC) and a global history register (hereinafter called a “branch history register (BHR)”) is popular as a tag for retrieving data from a BHT.
FIG. 1 explains branch prediction by a method using a branch history.
In FIG. 1, a BHT1 is a table for recording a tag, which is not shown in FIG. 1, based on fetched addresses and BHR information, and two-bit branch prediction information based on whether branch is conducted in the branch information of an address corresponding to the tag. A BHR2 is a plural-bit of register (in FIG. 1, five-bit) for recording what branch prediction is conducted in a plurality of branch instruction executed close at hand (in FIG. 2, five).
When conducting branch prediction, in the information processing device, a tag is generated from a fetched program counter value (FPC) and BHR information in the BHR2 at that time. The BHT1 is retrieved using this tag, and branch prediction is conducted based on branch prediction information read from the BHT1.
The BHT1 stores one of strongly not-taken, weakly not-taken, strongly taken and weakly taken as branch prediction information. Then, if the branch prediction information read from the BHT1 is either “strongly not-taken” or “weakly not-taken”, it is predicted to be “not-taken”, and if it is either “strongly taken” or “weakly taken”, it is predicted to be “taken”. The branch prediction information in the BHT1 continues to be successively updated based on whether branch is actually conducted. In the following description, if a branch instruction is branched or predicted to be branched, it is called “taken”, and if the branch instruction is not branched or predicted not to be branched, it is called “not-taken”.
When the result of the branch prediction is obtained, in the BHR2, the contents are shifted to the left by one bit, and the prediction result is set in the right-most bit. For example, branch (taken) is predicted, ‘1’ is set, and if non-branch (not-taken) is predicted, ‘0’ is set. In the following description, if ‘1’ is set in the right-most bit of BHR and shifted, it is called “1-shift”, and if 0 is set and shifted, it is called “0-shift”.
If branch prediction fails when a branch prediction method for advancing a process while predicting whether a branch instruction is branched when fetching an instruction is applied to a pipeline, a stage not related to the current process occurs in each slot of the pipeline, that is, a pipeline bubble occurs and performance greatly degrades.
Since in branch prediction, performance penalty due to failed prediction is heavy, in order to improve performance, prediction accuracy must be improved. In order to improve prediction accuracy, it is also important how to restore a state before branch prediction when failing in branch prediction.
For a branch prediction technology, a variety of proposals have been made, which includes a method disclosed by Japanese Patent Application No. H6-301534 (Information Processing Device).
Japanese Patent Application No. H6-301534 discloses a configuration with two execution pipelines of one for executing instructions before a branch instruction and the other for executing instructions after a branch instruction ahead. When failing in branch prediction, a state can be restored by switching pipelines.
As one using a branch history, Japanese Patent Application No. 2001-243069 (Branch Prediction Device and Method) discloses a method for bypassing the state transition of branch prediction to the branch prediction state of the same branch instruction on a pipeline in order to cope with the fact that the state transition of branch prediction information diverts from an actual branch operation.
In the method using a branch history, conventionally in the information processing device with a shallow pipeline structure, one cycle covers until a subsequent fetch is conducted after the BHT1 is retrieved and branch prediction is conducted. Therefore, the update control of FPC and BHR information was easy. However, recently it has become popular to improve performance by the use of an operation clock with a high frequency, and in order to improve performance, a control configuration with a deep pipeline has been used. Therefore, in such an information processing device, branch prediction is conducted across several cycles when fetching an instruction.
In the case of a deep pipeline, in the information processing device for conducting branch prediction by retrieving data from the BHT2 using an instruction fetch address (FPC) and a value in the BHR1, sometimes branch prediction is conducted a specific number of cycles later after starting an instruction fetch. In this case, when branch prediction fails, it is necessary to re-fetch after restoring the branch instruction to a state immediately after the failed branch prediction. For that purpose, information about a branch instruction must be stored in a branch instruction reservation station in advance, and when the failed branch prediction is determined, the branch instruction must be returned to the state where the fetch is conducted and re-fetched using the information stored in the reservation station.
In this case, BHR information must also be restored to the value used when fetching a branch instruction whose update control is not performed in each pipeline. However, if a pipeline is deep and fetch covers several cycles, as the BHR information, the pipeline states at the time of fetch cannot be all restored, and as the reproduction process of the BHR information, the BHR information is restored using the BHR information in the case where the branch prediction has failed is used without nay modifications.
However, in this case, since the BHR information in the case where fetching a branch instruction cannot be accurately restored, prediction accuracy degrades, which is a problem.